#include <iostream>
#include <vector>
using namespace std;

class bubble_sort
{
public:
    void sort(vector<int> &arr)
    {
        int n = arr.size();
        for (int i = 0; i < n; i++)
        {
            bool flag = false;
            for (int j = 0; j < n - i - 1; j++)
            {
                if (arr[j] > arr[j + 1])
                {
                    flag = true;
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
            if (!flag)
            {
                break;
            }
        }
        return;
    }
};

class q_sort
{
public:
    void sort(vector<int> &arr, int left, int right)
    {
        if (left >= right)
            return;

        int key = part_sort(arr, left, right);
        sort(arr, left, key - 1);
        sort(arr, key + 1, right);
    }

private:
    int part_sort(vector<int> &arr, int left, int right)
    {
        int key = left;
        while (left < right)
        {

            while (left < right && arr[right] >= arr[key])
            {
                right--;
            }
            while (left < right && arr[left] <= arr[key])
            {
                left++;
            }

            swap(arr[left], arr[right]);
        }
        swap(arr[left], arr[key]);
        return left;
    }
};

template <class T>
void Swap(T &a, T &b)
{
    T temp = a;
    a = b;
    b = temp;
}

class i_sort
{
public:
    void I_sort(vector<int> &arr)
    {
        for (int i = 1; i < arr.size() - 1; i++)
        {
            int end = i;
            int tmp = arr[i + 1];
            while (end >= 0)
            {
                if (arr[end] > tmp)
                {
                    arr[end + 1] = arr[end];
                }
                else
                {
                    break;
                }
                end--;
            }
            arr[end + 1] = tmp;
        }
    }
};

class S_sort
{
public:
    void sort(vector<int> &arr)
    {
        int gap = arr.size();
        while (gap > 1)
        {
            gap = gap / 2;
            for (int i = 0; i < arr.size() - gap; i += gap)
            {
                int end = i;
                int tmp = arr[i + gap];
                while (end >= 0)
                {
                    if (arr[end] > tmp)
                    {
                        arr[end + gap] = arr[end];
                    }
                    else
                    {
                        break;
                    }
                    end -= gap;
                }
                arr[end + gap] = tmp;
            }
        }
    }
};

class m_sort
{
public:
    void sort(vector<int> &arr)
    {
        vector<int> arr2(arr.size());
        _merge(arr,arr2,0,arr.size()-1);
    }

private:
    void _merge(vector<int>& arr,vector<int>& arr2,int left,int right)
    {
        if(left>=right) return;
        int mid=left+(right-left)/2;
        _merge(arr,arr2,left,mid);
        _merge(arr,arr2,mid+1,right);
        
        int begin1=left;
        int begin2=mid+1;
        int end1=mid;
        int end2=right;
        int pos=left;
        while(begin1<=end1 && begin2<=end2)
        {
            if(arr[begin1]>=arr[begin2])
            {
                arr2[pos++]=arr[begin2++];
            }else
            {
                arr2[pos++]=arr[begin1++];
            }
        }
        while(begin1<=end1)
        {
            arr2[pos++]=arr[begin1++];
        }
        while(begin2<=end2)
        {
            arr2[pos++]=arr[begin2++];
        }
        
        arr=arr2;
        return;
    }

};

int main()
{
    q_sort q;
    vector<int> arr = {
        1,
        2,
        3,
        9,
        4,
        5,
        6,
        7,
        8,
    };
    q.sort(arr, 0, arr.size() - 1);
    for (auto i : arr)
    {
        cout << i << " ";
    }

    vector<int> arr1 = {
        1,
        2,
        3,
        9,
        4,
        5,
        6,
        7,
        8,
    };
    swap(arr1[0], arr1[arr1.size() - 1]);

    return 0;
}